package com.example.demo.leetcode.codetop.bytedance;

/**
 * @author xujimou
 * @version 2.0
 * @Description
 * 给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
 *
 * 由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
 *
 * 注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：x = 4
 * 输出：2
 * 示例 2：
 *
 * 输入：x = 8
 * 输出：2
 * 解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/sqrtx
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @date 2022/2/22 11:30
 */
public class 算数平方根 {

    /**
     * @Desciption: 二分法
     * 10
     * 1 6 -> 3
     * 3 6 -> 4
     * 3 4 -> 3
     * 3 4 -> 3
     * @param x:
     */
    public static int mySqrt(int x) {

        int i =1,j=(x>>1)+1;
        while(i < j){
            int middle = (i+j) >> 1;
            if(x/middle == middle){
                return middle;
            }else if(x/middle > middle){
               i = middle;
            }else{
                j = middle;
            }
            if((j - i) == 1){
                return i;
            }
        }
        return x;
    }


    public static int myAdd(int a,int b){
        int x = a ^ b;
        int y = (a & b) << 1;
        if(y != 0){
            return myAdd(x,y);
        }
        return x;
    }

    /**
     * @Desciption:
     *  3*3 == 3(11)+6(110)=9
     * @param a:
     * @param b:
     */
    public static int myMultic(int a,int b){
        int res=0;
        while(b != 0){
            int temp = b & 1;
            if(temp != 0){
               res = myAdd(res,a);
            }
            a = a << 1;
            b = b >>> 1;
        }
        return res;
    }

    /**
     * @Desciption: 位运算实现除法
     * (1)保证都是整数 符号位 最后处理
     * (2)最后除数累乘
     * (3)注意边界问题，两个数都是整型最大值或者最小值的时候怎么办?
     * @param a:
     * @param b:
     */
    public static int divide(int a,int b){

        if(b == 0){
            return 0;
        }

        int sign = 1;
        if(a >0 && b <0){
            sign = -1;
        }else if(a< 0 && b >0){
            sign = -1;
        }
        a = a < 0? -a:a;
        b = b < 0 ?-b:b;
        int res = div(a, b);
        return sign > 0?res : -res;
    }

    public static int div(int a,int b){
        if(b > a){
            return 0;
        }
        int adderb = b;
        int count = 1;
        while(a >= adderb){
            adderb = adderb << 1;
            count = count << 1;
        }
        adderb = adderb >> 1;
        count = count >> 1;
        return count + div(a-adderb,b);
    }


    public static void main(String[] args) {
        System.out.println(mySqrt(2147395599));
        System.out.println(divide(12,4));
    }

}
